package com.guan.mysolutionstudy;

import org.junit.Test;

/**
 * @ClassName CountdownNodeList
 * @Author GuanCary
 * @Date 2020/5/14 15:47
 * @Version 1.0
 * 剑指offer: 输入一个链表，输出该链表中倒数第k个结点。
 * 思路:设计一个时间复杂度为n的方法,那就是直接用一个循环返回,我们设定两个节点,一个节点跑到了第K-1个元素,另一个节点开始跑
 * 最后第一个节点跑完后,第二个节点的当前指向就是倒数第K个节点
 * 我们知道倒数第K个节点就是正数第L长度+1-K个节点就是l+1-K个
 * 这个节点
 **/
public class CountdownNodeList {
    public ListNode solution(ListNode headNode, int k) {
        //排除错误参数
        if (headNode == null || k <= 0) {
            System.out.println("请检查输入的参数");
            return null;
        }
        ListNode node1;
        ListNode node2;
        node1 = headNode;
        node2 = headNode;
        //记录总节点数
        int countNum = 0;
        //后面验证用,别慌
        int index = k;
        while (node1 != null) {
            node1 = node1.next;
            countNum++;
            //当node1跑到第个k-1数时,node2开始跑
            //因为node1比node2多跑了k-1个节点
            //如果k-1跑完,当时的k应该为2,进行下一次循环,跑了K个点的时候,k为1,由于节点2一样也是从两个节点开始计数,所以
            //一开始就可以限制条件其实是k=0的时候才开始同步,当时是node1节点在第K+1个点
            //node1位k+1个节点,得到k=0后,node2直接获得两个节点,然后k在此递减
            //这里要想清楚,节点是从2开始计数,所以不着急跑,直接跑完k+1个数既k==0的时候的循环,那时候同步这个k==0的时候节点,
            //直接得到跑完两个节点,第一次k=0,因为他们跑的节点数的总和就是k+1
            if (k < 1) {
                node2 = node2.next;
            }
            //将k值递减,当跑了第k-1个数,node2开始跑节点
            k--;
        }
        //如果倒数的数还超过了countNum
        if (index > countNum) {
            System.out.println("倒数的次序超过人造链表总长度");
            return null;
        }
        System.out.println("倒数第" + index + "个数为" + node2.value);
        return node2;
    }

    @Test
    public void test() {
        //输入1314520
        solution(new ListNode(1, new ListNode(3, new ListNode(1, new ListNode(4, new
                ListNode(5, new ListNode(2, new ListNode(0))))))), 4);
        //输入1314520
        solution(new ListNode(1, new ListNode(3, new ListNode(1, new ListNode(4, new
                ListNode(5, new ListNode(2, new ListNode(0))))))), 7);
        //输入1314520
        solution(new ListNode(1, new ListNode(3, new ListNode(1, new ListNode(4, new
                ListNode(5, new ListNode(2, new ListNode(0))))))), 3);
        //输入1314520
        solution(new ListNode(1, new ListNode(3, new ListNode(1, new ListNode(4, new
                ListNode(5, new ListNode(2, new ListNode(0))))))), 2);
    }
}